package bTree.LeetCode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class 恢复二叉搜索树 {
    public void recoverTree(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode p = root;
        midLoop(list, p);
        List<Integer> list1 = new ArrayList<>(list);
        Collections.sort(list);
        int size = list.size();
        int[] arrays = new int[2];
        int cnt = 0;
        for (int i = 0; i < size; i++) {
            if (list.get(i) != list1.get(i)) {
                arrays[cnt++] = list1.get(i);
            }
        }
        midLoop2(p,arrays);
    }

    private void midLoop2(TreeNode p, int[] arrays) {
        if(p==null){
            return;
        }
        midLoop2(p.left,arrays);
        if(p.val==arrays[0]){
            p.val=arrays[1];
        }
        else if(p.val==arrays[1]){
            p.val=arrays[0];
        }
        midLoop2(p,arrays);
    }

    private void midLoop(List<Integer> list, TreeNode p) {
        if (p == null) {
            return;
        }
        midLoop(list, p.left);
        list.add(p.val);
        midLoop(list, p.right);
    }
}